package com.leetcode.algorithm.y22.m09.w2;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 543. 二叉树的直径
 * 
 * https://leetcode.cn/problems/diameter-of-binary-tree/
 * 
 * @author jie.deng
 *
 */
class Question0543Solution01 {

	public int diameterOfBinaryTree(TreeNode root) {
		int[] diameter = new int[] { 0 };
		getHeight(root, diameter);
		return diameter[0];
	}

	private int getHeight(TreeNode root, int[] diameter) {
		if (root == null) {
			return 0;
		}
		int heightL = getHeight(root.left, diameter);
		int heightR = getHeight(root.right, diameter);
		if (heightL + heightR > diameter[0]) {
			diameter[0] = heightL + heightR;
		}
		return Math.max(heightL, heightR) + 1;
	}

}